package com.wkq;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * 通过递归实现的二分搜索树
 *
 * @param <E>
 */
public class BinarySearchTreeR<E extends Comparable<E>> implements BST<E> {

    private class Node {
        public E e;
        public Node left;
        public Node right;
        //以该节点为艮的子树节点总数
        public int n;

        public Node(E e, int n) {
            this.e = e;
            this.n = n;
        }

        @Override
        public String toString() {
            return e.toString();
        }
    }

    private Node root;
    private int size;

    public BinarySearchTreeR() {
        this.root = null;
    }

    @Override
    public int getSize() {
        return root.n;
    }

    @Override
    public boolean isEmpty() {
        return getSize() == 0;
    }

    @Override
    public void add(E e) {
        root = add(root, e);
    }

    private Node add(Node node, E e) {
        if (node == null) return new Node(e, 1);
        if (e.compareTo(node.e) < 0) {
            node.left = add(node.left, e);
            node.n = node.n + 1;
        } else {
            node.n = node.n + 1;
            node.right = add(node.right, e);
        }
        return node;
    }

    @Override
    public boolean contains(E e) {
        return contains(root, e);
    }

    private boolean contains(Node node, E e) {
        if (node == null) return false;
        if (node.e.compareTo(e) == 0) return true;
        if (node.e.compareTo(e) < 0) return contains(node.right, e);
        return contains(node.left, e);
    }

    @Override
    public void prevOrder() {
        prevOrder(root);
    }

    private void prevOrder(Node node) {
        if (node == null) return;
        System.out.print(node.e + "  ");
        prevOrder(node.left);
        prevOrder(node.right);
    }

    @Override
    public void inOrder() {
        inOrder(root);
    }

    private void inOrder(Node node) {
        if (node != null) {
            inOrder(node.left);
            System.out.print(node + "  ");
            inOrder(node.right);
        }
    }

    @Override
    public void postOrder() {
        postOrder(root);
    }

    private void postOrder(Node node) {
        if (node != null) {
            postOrder(node.left);
            postOrder(node.right);
            System.out.print(node.e + "  ");
        }
    }

    @Override
    public void levelOrder() {
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            Node curr = queue.poll();
            System.out.print(curr.e + "   ");
            if (curr.left != null) queue.add(curr.left);
            if (curr.left != null) queue.add(curr.right);
        }

    }

    @Override
    public void remove(E e) {

    }

    public static void main(String[] args) {
        BST<Integer> binarySearchTree = new BinarySearchTreeR<>();
        int[] nums = {5, 3, 6, 8, 4, 2};
        for (int num : nums) {
            binarySearchTree.add(num);
        }

        int size = binarySearchTree.getSize();
        System.out.println(size);
        binarySearchTree.levelOrder();
        System.out.println("binarySearchTree = " + binarySearchTree.getSize());
        System.out.println("binarySearchTree.contains(2) = " + binarySearchTree.contains(2));
        System.out.println("binarySearchTree.contains(2) = " + binarySearchTree.contains(11));
        binarySearchTree.prevOrder();
        System.out.println();
        binarySearchTree.inOrder();
        System.out.println();
        binarySearchTree.postOrder();

    }
}
